/**
 * 给一个字符串，问有多少个子串可以被子串的最后一位整除，允许有前导0
 * 可以分情况讨论，因为只有7比较麻烦，需要用同模前缀和。其余数字结尾的情况均可以在当前位置O(1)解决
 * 但是既然用到了同模前缀和，可以所有数字一起用。
 * 令 Dijk 是i位置除以j模k的字符串数量，使用刷表法：
 * D[i+1][j][(k*10+c)%j] += Dijk
 * 其中c是当前位置的数字
 * 注意每一步迭代之前相当于有一个初始化：D[i+1][j][c%j] = 1
 * 然后答案就是累加和： D[i][c][0]
 * 还可以滚动优化，字符串达到1E6可能需要
 */
class Solution {
public:
    long long countSubstrings(string s) {
        int N = s.length();    
        vector<array<array<int, 10>, 10>> D(N + 1, array<array<int, 10>, 10>{});
        for(int i=0;i<N;++i){
            int c = s[i] - '0';
            const auto & pre = D[i];
            auto & d = D[i + 1];
            
            for(int j=1;j<10;++j){     
                d[j][c % j] = 1;          
                for(int k=0;k<10;++k){
                    d[j][(k * 10 + c) % j] += pre[j][k];
                }
            }
        }
        long long ans = 0;
        for(int i=1;i<=N;++i){
            auto c = s[i - 1] - '0';
            ans += D[i][c][0];
        }
        return ans;
    }
};